package 数据结构.栈_队列;

import java.util.Stack;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-24
 */
public class JZ31栈的压入弹出序列 {
    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    //辅助栈
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int n = pushA.length;
        Stack<Integer> s = new Stack<>();

        int j = 0;
        for(int i=0;i<n;i++){
            while(j<n && (s.isEmpty() || s.peek() != popA[i])){
                s.push(pushA[j]);
                j++;
            }
            if(s.peek() == popA[i]){
                s.pop();
            }else{
                return false;
            }
        }
        return  true;
    }

    //原地栈
    public boolean IsPopOrder2(int [] pushA,int [] popA) {
//        step 1：用下标n表示栈空间，用j表示出栈序列的下标。
        int n = 0;
        int j = 0;
//        step 2：遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
        for (int num : pushA){
            pushA[n] = num;
            //        step 3：当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
            while (n >= 0 && pushA[n] == popA[j]){
                j++;
                n--;
            }
            n++;
        }

//        step 4：最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。
        return n == 0;
    }
}
